/*
约瑟夫环-(数组、循环链表、数学)
约瑟夫环（约瑟夫问题）是一个数学的应用问题：
已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。
从编号为s的人开始报数，数到m的那个人出列；
他的下一个人又从1开始报数，数到m的那个人又出列；
依此规律重复下去，直到圆桌周围的人全部出列。
模拟过程，求出最后的人。
*/

#include <stdio.h>
#include <stdlib.h>

#define Status int
#define OK 1
#define ERROR 0

typedef struct node
{
    int data;
    struct node *next;
}Node;

void Josephus(Node ** list,int n,int m,int s);
void PushBackList(Node ** list, int data);
void DeleteList(Node ** list, int data);
int DeleteListIndex(Node ** list, int index);
void FreeList(Node ** list);
void ListPrint(Node ** list);
int LenList(Node ** list);

int main()
{

    Node *head;
    Node **gg = &head;
    for(int i = 0; i < 10; i++) PushBackList(gg, i+1); // 编号
    ListPrint(gg);
    printf("\n");
    Josephus(gg, 10, 3, 4);
    return 0;
}

//已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。
//从编号为s的人开始报数，数到m的那个人出列；
//他的下一个人又从1开始报数，数到m的那个人又出列；
void Josephus(Node ** list,int n,int m,int s)
{
    while(n > 1)
    {
        int r = DeleteListIndex(list, (m-1+s-1) % n);
        printf("del num: %d\n", r);
        ListPrint(list);

        s = (m-1+s-1) % n + 1;
        n--;
        printf("\n");
    }
    printf("finish %d\n", (*list)->data);
}

void PushBackList(Node ** list, int data)
{
    Node * newblock = (Node *)malloc(sizeof(Node));
    if(!newblock) return;
    newblock->data = data;
    newblock->next = NULL;

    Node * head = (*list);
    if(head == NULL)
        *list = newblock;
    else{
        while(head->next)
        {
            head = head->next;
        }
        // last
        head->next = newblock;
    }
}

void DeleteList(Node ** list, int data)
{
    Node *head = *list;
    Node *last = *list;
    while(head)
    {
        if(head->data == data)
        {
            if(head == last) // first
            {
                Node * temp = head;
                *list = head->next;
                free(temp);
                return;
            }
            else{
                last->next = head->next;
                free(head);
                return;
            }
        }
        last = head;
        head = head->next;
    }
}

void ListPrint(Node ** list)
{
    Node *head = *list;
    while(head)
    {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

void FreeList(Node ** list)
{
    Node *head = *list;
    Node *temp = NULL;
    while(head)
    {
        temp = head;
        head = head->next;
        free(temp);
    }
    *list = NULL;
}

int LenList(Node ** list)
{
    int size = 0;
    Node *head = *list;
    while(head)
    {
        size++;
        head = head->next;
    }
    return size;
}

int DeleteListIndex(Node ** list, int index)
{
    int size = 0;
    Node *head = *list;
    Node *last = *list;
    while(head)
    {
        if(size == index)
        {
            if(head == last) // first
            {
                Node * temp = head;
                int r = temp->data;
                *list = head->next;
                free(temp);
                return r;
            }
            else{
                last->next = head->next;
                int r = head->data;
                free(head);
                return r;
            }
        }
        last = head;
        head = head->next;
        size++;
    }
    return 0;
}
